package extract;

import java.util.ArrayList;
import java.util.Random;

/**
 * @author Zerone
 * date: 2016/11/8
 *
 * Fingerprint extraction: convert time domain data to frequency domain data
 * per frame.Find and record the strongest N frequencies per frame. Calculated
 * the combined hash for these frequencies. Call the database function to store
 * in the database.
 */

public class Fingerprint {
    // DO NOT write FFT.WINDOW_SIZE / 44100, it equals to 0 forever!!
    //public static final double scaling = 4096 / 44100.0;
    public static final int N = 2;
    private ArrayList<int[]> constel_data = new ArrayList<>();

    /**
     * quicksort's partition function
     *
     * @param a The array
     * @param p The starting index
     * @param r The ending index
     * @return
     */
    private static int partition(double a[], int p, int r) {
        double x = a[r];
        int i = p - 1;
        for (int j = p; j < r; ++j) {
            if (a[j] <= x) {
                i++;
                double temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        double temp = a[i + 1];
        a[i + 1] = a[r];
        a[r] = temp;
        return i + 1;
    }

    /**
     * randomly partition function
     *
     * @param a The array
     * @param p The starting index
     * @param r The ending index
     * @return
     */
    private static int random_partition(double a[], int p, int r) {
        int i = p + new Random().nextInt(r - p + 1);
        double temp = a[i];
        a[i] = a[r];
        a[r] = temp;
        return partition(a, p, r);//调用划分函数
    }

    /**
     * find the i th small number
     *
     * @param a The array
     * @param p The starting index
     * @param r The ending index
     * @param i The i
     * @return The i th small number in the array a.
     */
    private static double random_select(double a[], int p, int r, int i) {
        if (p == r) {
            return a[p];
        }
        int q = random_partition(a, p, r);
        int k = q - p + 1;
        if (k == i) {
            return a[q];
        } else if (i < k) {
            return random_select(a, p, q - 1, i);
        } else {
            return random_select(a, q + 1, r, i - k);
        }
    }

    /**
     * Append a column of frequency peaks to the constellation map.
     * A frequency peak is a frequency value whose amplitude is the highest among
     * all frequencies in a frequency interval.
     *
     * @param freqDomain The frequency domain generated by FFT.
     */
    public void append(double[] freqDomain) {
        int[] freqPeaks = new int[N];
        int length = 512;
        ArrayList<Double> copy = new ArrayList<>();
        double[] data = new double[512];


        for (int i = 0; i < 512; ++i) {
            // intercept the first 512 data to find the highest amplitude
            data[i] = freqDomain[i];

            /**
             * copy the original array to obtain the corresponding frequency
             * because after calling the random_select function, the original
             * array has been sorted.
             */
            copy.add(data[i]);
        }
        freqDomain = null;

        /**
         * TODO: Either find N frequencies with the highest amplitude(energy),
         * or find the frequency with the max energy within each interval.
         */
        for (int i = 0; i < N; ++i) {
            freqPeaks[i] = copy.indexOf(random_select(data, 0, length - 1, length - (i + 1) + 1));
        }
        copy.clear();
        constel_data.add(freqPeaks);
    }

    /**
     * Generate fingerprints using Combinational Hash.
     * For each frequency peak, generate 6 fingerprints with its 6 successors.
     *
     * @return
     */
    public ArrayList<ShazamHash> combineHash() {
        if (constel_data.size() < 3)
            throw new RuntimeException("Too few frequency peaks");

        ArrayList<ShazamHash> hashes = new ArrayList<>();
        for (int i = 0; i < constel_data.size() - 2; ++i) {
            for (int k = 0; k < N; ++k) {
                // "Combine" with all peak frequencies inside its next two frames.
                for (int j = 1; j <= 2; ++j) {
                    for (int kk = 0; kk < N; ++kk) {
                        ShazamHash hash = new ShazamHash();
                        hash.f1 = (short) constel_data.get(i)[k];
                        hash.f2 = (short) constel_data.get(i + j)[kk];
                        hash.dt = (short) j;
                        hash.offset = i;
                        hashes.add(hash);
                    }
                }
            }
        }
        return hashes;
    }
}